package leetcode.f1t100;

/**
 * 判断两个字符串是否可以通过切分旋转的方式由A->B
 * https://leetcode.com/problems/scramble-string/
 *
 * @author lichx
 * @createTime 2024/1/31 10:20
 */
public class Q87_ScrambleString {

    public static void main(String[] args) {
        Q87_ScrambleString bean = new Q87_ScrambleString();
        System.out.println(bean.isScramble("abcde", "caebd"));
    }

    public boolean isScramble(String s1, String s2) {
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        if (chars1.length != chars2.length) {
            return false;
        }
//        return isScrambleRecursion(chars1, 0, chars1.length, chars2, 0 , chars2.length);
//        return isScrambleCache(chars1, 0, chars1.length, chars2, 0 , chars2.length,
//                new int[chars1.length+1][chars1.length+1][chars1.length+1][chars1.length+1]);
//        return isScrambleCacheLess(chars1, 0, chars1.length, chars2, 0 ,
//                new int[chars1.length+1][chars1.length+1][chars1.length+1]);
        return isScrambleDp(chars1, chars2);
    }

    private boolean isScrambleDp(char[] chars1, char[] chars2) {
        boolean[][][] dp = new boolean[chars1.length + 1][chars1.length + 1][chars1.length + 1];
        for (int i = 0; i < chars1.length; i++) {
            for (int j = 0; j < chars2.length; j++) {
                dp[1][i][j] = chars1[i] == chars2[j];
            }
        }
        for (int h = 2; h <= chars1.length; h++) {
            for (int l = 1; l < h; l++) {
                for (int i = 0; i < chars1.length; i++) {
                    for (int j = 0; j < chars2.length; j++) {
                        if (i + l > chars1.length) {
                            continue;
                        }
                        if (j + l > chars2.length) {
                            continue;
                        }
                        boolean ll = dp[l][i][j];
                        boolean rr = dp[h - l][i + l][j + l];
                        dp[h][i][j] = dp[h][i][j] || ll && rr;

                        if (j + h - l > chars1.length) {
                            continue;
                        }
                        boolean lr = dp[l][i][j + h - l];
                        boolean rl = dp[h - l][i + l][j];
                        dp[h][i][j] = dp[h][i][j] || lr && rl;
                    }
                }
            }
        }
        return dp[chars1.length][0][0];
    }

    public boolean isScrambleCacheLess(char[] chars1, int l1, int len, char[] chars2, int l2, int[][][] cache) {
        if (cache[l1][l2][len] != 0) {
            return cache[l1][l2][len] == 1;
        }
        if (len == 1) {
            boolean result = chars1[l1] == chars2[l2];
            cache[l1][l2][len] = result ? 1 : 2;
            return result;
        }
        for (int i = 1; i < len; i++) {
//            if (isScrambleCacheLess(chars1, l1, i, chars2, l2, cache)
//                    && isScrambleCacheLess(chars1, l1 + i, len - i, chars2, l2 + i, cache)
//                    || isScrambleCacheLess(chars1, l1, i, chars2, len - i + l2, cache)
//                    && isScrambleCacheLess(chars1, l1 + i, len - i, chars2, l2, cache)) {
//                cache[l1][l2][len] = 1;
//                return true;
//            }
            boolean ll = isScrambleCacheLess(chars1, l1, i, chars2, l2, cache);
            boolean rr = isScrambleCacheLess(chars1, l1 + i, len - i, chars2, l2 + i, cache);
            boolean lr = isScrambleCacheLess(chars1, l1, i, chars2, len - i + l2, cache);
            boolean rl = isScrambleCacheLess(chars1, l1 + i, len - i, chars2, l2, cache);
            if (ll && rr || lr && rl) {
                cache[l1][l2][len] = 1;
                return true;
            }
        }
        cache[l1][l2][len] = 2;
        return false;
    }

    public boolean isScrambleCache(char[] chars1, int l1, int r1, char[] chars2, int l2, int r2, int[][][][] cache) {
        if (cache[l1][r1][l2][r2] != 0) {
            return cache[l1][r1][l2][r2] == 1;
        }
        if (r1 - l1 == 1) {
            boolean result = chars1[l1] == chars2[l2];
            cache[l1][r1][l2][r2] = result ? 1 : 2;
            return result;
        }
        int length = r1 - l1;
        for (int i = 1; i < length; i++) {
            if (isScrambleCache(chars1, l1, l1 + i, chars2, l2, l2 + i, cache)
                    && isScrambleCache(chars1, l1 + i, r1, chars2, l2 + i, r2, cache)
                    || isScrambleCache(chars1, l1, l1 + i, chars2, r2 - i, r2, cache)
                    && isScrambleCache(chars1, l1 + i, r1, chars2, l2, r2 - i, cache)) {
                cache[l1][r1][l2][r2] = 1;
                return true;
            }
        }
        cache[l1][r1][l2][r2] = 2;
        return false;
    }

    public boolean isScrambleRecursion(char[] chars1, int l1, int r1, char[] chars2, int l2, int r2) {
        if (r1 - l1 == 1) {
            return chars1[l1] == chars2[l2];
        }
        int length = r1 - l1;
        for (int i = 1; i < length; i++) {
            if ((isScrambleRecursion(chars1, l1, l1 + i, chars2, l2, l2 + i)
                    && isScrambleRecursion(chars1, l1 + i, r1, chars2, l2 + i, r2))
                    || (isScrambleRecursion(chars1, l1, l1 + i, chars2, r2 - i, r2)
                    && isScrambleRecursion(chars1, l1 + i, r1, chars2, l2, r2 - i))) {
                return true;
            }
        }
        return false;
    }
}
